package sword_offer;

/**
 * @ClassName _53_1_search
 * @Description: 统计一个数字在排序数组中出现的次数。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *  
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 *  
 *
 * 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:34
 */
public class _53_1_search {

    public static void main(String[] args) {
//        int[] nums = new int[]{5,7,7,8,8,10};
        int[] nums = new int[]{2,2};
        int search = new _53_1_search().search(nums, 2);
        System.out.println(search);
    }

    public int search(int[] nums, int target) {
        // 校验是否在数组范围内
        if (nums.length == 0 || nums[nums.length - 1] < target || nums[0] > target)
            return 0;

        // 找到第一次出现的位置 和最后一次出现的位置
        int head = 0, tail = nums.length - 1, first = -1, last = -1;

        while (head < tail){
            int mid = head + (tail - head >> 1);
            if (nums[mid] > target){
                tail = mid - 1;
            }else if (nums[mid] < target){
                head = mid + 1;
            }else {
                tail = mid;
            }
        }
        if (nums[head] == target){
            first = head;
        }else if (nums[tail] == target){
            first = tail;
        }else {
            return 0;
        }


        head = 0;
        tail = nums.length - 1;
        while (head + 1 < tail){
            int mid = head + (tail - head >> 1);
            if (nums[mid] > target){
                tail = mid - 1;
            }else if (nums[mid] < target){
                head = mid + 1;
            }else {
                head = mid;
            }
        }
        if (nums[tail] == target){
            last = tail;
        }else{
            last = head;
        }
        return last - first + 1;
    }
}
